#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <string>
using namespace std;

class Solution
{
public:
    string longestPalindrome(string s)
	{
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
		//preprocess
		string ss(s.size() * 2 + 1,'#');
		for(size_t i=0;i<s.size();i++)
			ss[2*i+1] = s[i];

		int* counts = new int[ss.size()];
		counts[0] = 0;
		size_t rightEdge = 0,center=0;
		int maxD = 0;
		size_t maxPos = 0;
		for(size_t i = 1;i<ss.size();i++)
		{
			if(i<rightEdge && (counts[2*center-i]+i)<rightEdge)
				counts[i] = counts[2*center-i];
			else
			{
				if(i<rightEdge)
					counts[i] = rightEdge-i+1;
				else
					counts[i] = 1;

				while(((i+counts[i])<ss.size()) && ((i>=counts[i])) && (ss[i+counts[i]]==ss[i-counts[i]]))
					counts[i]++;
				counts[i]--;

				if((i+counts[i])>rightEdge)
				{
					center = i;
					rightEdge = i+counts[i];
				}
			}

			if(counts[i] > maxD)
			{
				maxD = counts[i];
				maxPos = i;
			}
		}
		
		string result;
		if(ss[maxPos]=='#')
		{
			maxD = maxD / 2 + maxD % 2;
			result = s.substr(maxPos/2-maxD,2*maxD);
		}
		else
		{
			maxD = maxD / 2;
			result = s.substr((maxPos-1)/2 - maxD,2*maxD+1);
		}
		delete [] counts;
		return result;
    }
};
#endif
